3.6 Bounded Queues (b_queue)

b_queue E

1. Definition

An instance Q of the paramerized data type is a queue (see section 2.4) of bounded size.


2. Creation

Q (n)

creates an instance of type that can hold up to n elements. is initialized with the empty queue.


3. Operations & truecm & truecm & E top returns the front element of Q is not empty.

E pop deletes and returns the front element of Q is not empty.

void append E x appends x to the rear end of Q.size()< n.

void clear makes the empty queue.

int size returns the size of .

bool empty returns true if is empty, false otherwise.


4. Implementation

Bounded Queues are implemented by circular arrays. All operations take time O(1). The space requirement is O(n).